package org.cy.algorithm.chapter_04;

import org.cy.algorithm.util.AlgorithmUtil;

import static org.cy.algorithm.chapter_04.MaxSubSum.divideRecuse;

public class MaxSubSum_4_1_5 {

    public static MaxSubSum.Result linearSolution(int[] nums) {
        MaxSubSum.Result result = new MaxSubSum.Result();
        if (nums == null || nums.length == 0) {
            return result;
        }

        // A[0..i-1] 已经算出了最长子序和，那么问题编程增加A[i]后，最长子序和要如何调整？
        for (int i = 0; i < nums.length; i++) {
            if (result.start == -1) {
                // 如果是第一个大于0的元素，将其设置为result
                if (nums[i] > 0) {
                    result.start = i;
                    result.end = i;
                    result.sum = nums[i];
                }
            } else if (result.end == i - 1) {
                // 如果A[i-1]是end，那么如果当前值为正，则将该元素加入到列表中
                if (nums[i] > 0) {
                    result.end = i;
                    result.sum += nums[i];
                }
            } else {
                // 如果A[i-1]之前的元素是end，那么从i开始向前计算，找出A[0..i]的最长子序和，保持A[0..i]和A[0..i-1]具有相同性质。
                int sum = 0;
                int max = 0;
                int left = -1;
                int right = i;
                for (int j = i; j >= 0; j--) {
                    sum += nums[j];
                    if (sum > max) {
                        max = sum;
                        left = j;
                    }
                }

                if (max > result.sum) {
                    result = new MaxSubSum.Result(left, right, max);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 1000; i++) {
            int[] randomArray = AlgorithmUtil.createRandomArray(100);
            MaxSubSum.Result resultLinear = linearSolution(AlgorithmUtil.copyArray(randomArray));
            MaxSubSum.Result divideRecuse = divideRecuse(AlgorithmUtil.copyArray(randomArray));
            if (divideRecuse.sum != resultLinear.sum) {
                AlgorithmUtil.printArray(randomArray);
                System.out.println(resultLinear);
                System.out.println(divideRecuse);
                System.out.println("Oops");
                return;
            }
        }
        System.out.println("OK");
    }
}
